Application of Graph Theory to Find Minimal Paths Between Two Places for the Transportation Problem

Abstract

Graph theory is used for finding communities in networks. Graphs are used as device for modeling and description of real world network systems such are: transport, water, electricity, internet, work operations schemes in the process of production, construction, etc. Although the content of these schemes differ among themselves, but they have also common features and reflect certain items that are in the relation between each other. In this paper, we study on how graph theory can generate transportation problem using shortest path, we designed the solution for practical problem to find a Minimum Spanning Tree(MST) by using Kruskal’s Algorithm and minimal path between two places and graph search Dijkstra’s algorithm.

Introduction

I. INTRODUCTION

Graph theory provides many useful applications in Operations research. Graph theory is the study of points and lines. In particular it involves the ways in which sets of points called nodes or vertices. It can be connected by lines called edges or arcs. Graphs in this context differ from the more familiar co-ordinates plot that portay mathematical relations and functions. In this paper for a given graph find a minimum cost to find the minimal path between two places. There are different path options to reach from Place A to Place B, but our aim is to find the minimal path with a minimum transportation costs, this requires a lot efforts.

1. Collection of points
2. Collection of lines
3. Points sets in non empty

In this paper for a given graph we find a minimal path of Transportation problem.

III. MINIMUM SPANNIG TREE (MST):

A minimum Spanning Tree(MST) is a subset of edges of a connected weighted undirected graph that connects all the vertices together with the minimum possible total edge weight. To derive an MST, Kruskal’s algorithm can be used.

A. Kruskal’s Algorithm

Let T = Empty Spanning Tree

      E = Set of Edges

      N = Number of nodes in graph

While T has fever then N-1 edges. { Remove an edge (v, w) of lowest cost (arc or edge) from E. If adding (v, w) to T would create a cycle then discard (v, w) to T}.   

B. Minimum Spanning tree by using Kruskal’s Algorithm:

In this paper the Minimum Spanning tree for the given case is described by several figures given in the following.

Firstly are used all nodes of the given graph without arches, then we will start to put arcs in their place starting from the lowest cost (arc length 1) to the one with higher costs, but having in mind not to create cycles (Figure 3). This process continues by placing the second arc of length 2 (Figure 4).

V. DIJSKTRA’S ALGORITHM

Dijkstra’s algorithm is the iterative algorithmic process to provide us with the minimal path from one specific starting node to all other nodes of a graph. It is different from the minimum spanning tree as the shortest distance among two vertices might not involve all the vertices of the graph.

By using Dijsktra’s algorithm we are able to find the minimal distances (length of arc) from a place to all other nodes. Firstly, we start from the Place A, which is chosen as permanent Place(node). Analyzing the distances of the neighbourhoods Place(nodes) of the Place (node) A, we are able to find the minimal path to Place 2 (its distance is equal with 2). Afterwards Place 2 is chosen as permanent Place and we have to check the distances from Place 2 to the neighbour Places. To the each neighbour Place is added the length of the permanent Place.

VII. ACKNOWLEDGEMENT

Thank you to M.RAMYA , Assistant professor in Department of Mathematics at Dr SNS Rajalakshmi College of Arts and Science who has supported this research.

Conclusion

Dijkstra\'s algorithm will find the shortest path between two Places(nodes).The results which are obtained for the given example shows that Algorithm Dijsktra is very effective tool to find the path with lowest cost from Place A to Place B. Same results have been obtained also for Minimum Spanning Tree by using Kruskal algorithm, but this case the procedure is much simpler with a minimum spanning tree to reach node B from node A with the lowest total cost. We have tried also to find the worst scenario to reach node B from node A which is approximately 63% more expensive from the first case.

References

[1] A.Arockiamary, G.Pravina, Application of Graph theory to find shortest path of transportation problem. Email: arockia68@gmail.com , pravinahus@gmail.com [2] Vitala seta,Finding the shortest path using dijkstra’s algorithm,IJIRMPS Volume 9,September 2021 ISSN:2349-7300 [3] T.Neumann,Routing planning as an application of graph theory with fuzzy logic, volume 10 number 4 [4] Xiao Zhu WANG(2018),The comparison of three algorithm in shortest path issue, IOP Publishing, China [5] S.Pavithra, K.M.Manikandan, Application of graph theory to find optimal path and minimized time for the transportation problem, IJSRP Volume 11, Issue 1, January 2021, ISSN 2250-3153

Copyright

Copyright © 2022 Nandhini M, Ramya M. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.